package com.wpw.web;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 笛卡尔积工具类
 * @ClassName: DilkajiUtil
 * @CreateDate: 2020-01-13 17:04
 * @author: wu*/
public class DilkajiUtil {

    /**
     * @Description: 找到笛卡尔积中是否存在和为sum的
     * @Title: getDescartes
     * @author: wupengwei
     * @CreateDate: 2020-01-13 18:03
     * @param list
     * @param sum
     * @return
     * @throws
     */
    public static Boolean getDescartes(List<List<String>> list, Integer sum) {
        return descartesRecursive(list, 0, new ArrayList<String>(), sum);
    }

    /**
     * 递归实现
     * 原理：从原始list的0开始依次遍历到最后
     *
     * @param originalList 原始list
     * @param position     当前递归在原始list的position
     * @param cacheList    临时保存的list
     */
    private static Boolean descartesRecursive(List<List<String>> originalList, int position, List<String> cacheList, Integer sum) {
        List<String> originalItemList = originalList.get(position);
        for (int i = 0; i < originalItemList.size(); i++) {
            //最后一个复用cacheList，节省内存
            List<String> childCacheList = (i == originalItemList.size() - 1) ? cacheList : new ArrayList<>(cacheList);
            childCacheList.add(originalItemList.get(i));
            if (position == originalList.size() - 1) {//遍历到最后退出递归
                //returnList.add(childCacheList);
                int curSum = 0;
                for (String s : childCacheList) {
                    curSum = curSum + Integer.parseInt(s);
                }
                if (sum.equals(curSum)) {
                    //
                    System.out.println("命中" + childCacheList);
                    //直接返回
                    return true;
                }


                continue;
            }
            Boolean aBoolean = descartesRecursive(originalList, position + 1, childCacheList, sum);
            if (aBoolean) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<List<String>> listData = new ArrayList<>();
        List<String> list1 = new ArrayList<>();
        for (int i = 1; i <= 703; i++) {
            list1.add(String.valueOf(i));
        }
        listData.add(list1);

        listData.add(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));
        listData.add(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));
        listData.add(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));
        listData.add(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));
        listData.add(Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", "10"));

        int count = 1;
        for (List<String> listDatum : listData) {
            count = count * listDatum.size();
        }

        System.out.println("共" + count);
        System.out.println("集合为:" + listData);
        long start = System.currentTimeMillis();
        Boolean descartes = getDescartes(listData, 753);
        System.out.println("结果：" + descartes);
        System.out.println("耗时：" + (System.currentTimeMillis() - start) + "ms");
    }
}